#include<iostream>
#include<vector>
#include<stack>
#include<string>
#include<queue>
#include<algorithm>
#include<unordered_set>
using namespace std;


class Node{
    public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val){
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbor){
        val = _val;
        neighbors = _neighbor;
    }
};

class Solution{
    private:
    unordered_map<int, Node*> G;
    unordered_map<Node*, Node*> visit;

    public:
    //dfs
    Node* ans1(Node* node){
        if(node == nullptr){
            return node;
        }
        if(visit.find(node) != visit.end()){
            return visit[node];
        }

        Node* cloneNode = new Node(node->val);
        visit[node] = cloneNode;
        for(auto& neighbor: node->neighbors){
            cloneNode->neighbors.emplace_back(ans1(neighbor));
        }

        return cloneNode;
    }

    //bfs
    Node* ans2(Node* node){
        if(node == nullptr){
            return node;
        }

        unordered_map<Node*, Node*> Grpah;

        queue<Node*> Q;
        Q.push(node);
        Grpah[node] = new Node(node->val);

        while(!Q.empty()){
            auto n = Q.front();
            Q.pop();
            for (auto& neighbor: n->neighbors) {
                if (Grpah.find(neighbor) == Grpah.end()) {
                    Grpah[neighbor] = new Node(neighbor->val);
                    Q.push(neighbor);
                }

                Grpah[n]->neighbors.emplace_back(Grpah[neighbor]);
            }
        }

        return Grpah[node];
    }

    Node* create_graph(vector<vector<int>> adjList){
        int len = adjList.size();
        for(int i = 0; i != len; i++){
            Node* node = new Node();
            G[i+1] = node;
        }
        for(int i = 0; i != len; i++){
            int neg = adjList[i].size();
            vector<Node*> temp;
            for(int j = 0; j != neg; j++){
                temp.push_back(G[adjList[i][j]]);
            }
            G[i+1]->val = i+1;
            G[i+1]->neighbors = temp;
        }

        return G[1];
    }

};



void test1(){
    vector<vector<int>> graph = {
        {2,4},
        {1,3},
        {2,4},
        {1,3}
    };

    Solution s;
    Node* G = s.create_graph(graph);
    Node* ret = s.ans2(G);
    
    
}

void test2(){
    vector<vector<int>> grid = {
        {}
    };

    Solution s;
    
}



int main(void){
    test1();
    cout << "-----------------------------" << endl;
    test2();

    return 0;
}